import java.util.ArrayList;
import java.util.List;

/**
 * @author SaoE
 * @date 2025/2/25 16:22
 */
public class _22 {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>(); // 将 res 改为局部变量
        backTrace(n, n, new StringBuilder(), res);
        return res;
    }

    public void backTrace(int leftNum, int rightNum, StringBuilder path, List<String> res) {
        // 如果左括号和右括号都用完了，说明找到一个有效组合
        if (leftNum == 0 && rightNum == 0) {
            res.add(path.toString());
            return;
        }

        // 如果还有左括号可用，尝试添加左括号
        if (leftNum > 0) {
            path.append("(");
            backTrace(leftNum - 1, rightNum, path, res);
            path.deleteCharAt(path.length() - 1); // 回溯，删除最后一个字符
        }

        // 如果右括号比左括号多，尝试添加右括号
        if (rightNum > leftNum) {
            path.append(")");
            backTrace(leftNum, rightNum - 1, path, res);
            path.deleteCharAt(path.length() - 1); // 回溯，删除最后一个字符
        }
    }

    public static void main(String[] args) {
        _22 v = new _22();
        System.out.println(v.generateParenthesis(3));
    }
}
